/*
** Copyright (C) 2009 Joshua Brent Marsh <joshua@icub3d.com>
**  
** This file is part of icub3d-adt
**
** icub3d-adt is free sofware; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 3 of the License, or
** (at your option) any later version.
**  
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**  
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**  
*/

/* $Id: btree_funcs.c 36 2009-11-02 15:06:50Z joshua@icub3d.com $ */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <malloc.h>
#include <assert.h>

#include "btree.h"
#include "btree_funcs.h"
#include "rbbtree_funcs.h"

struct btree_node * 
new_node (void *data, struct btree_node *left,
	  struct btree_node *right)
{
  struct btree_node * new_node;

  /* Make the new node. */
  new_node = malloc (sizeof (struct btree_node));
  if (new_node == NULL)
    {
      return NULL;
    }

  new_node->data = data;

  /* Like the left node if we got one. */
  new_node->left = left;
  if (left != NULL)
    left->parent = new_node;

  /* Like the right node if we got one. */
  new_node->right = right;
  if (right != NULL)
    right->parent = new_node;

  /* Parent starts null. It will be set elsewhere. */
  new_node->parent = NULL;
  
  return new_node;
}

struct btree_node * 
probe (Btree *btree, void *data)
{
  struct btree_node *cur;
  int result;

  assert (btree != NULL);
  assert (data != NULL);

  cur = btree->root;

  /* We are going to traverse the tree until we find the node or get to a 
     leaf. */
  while (cur != NULL)
    {
      result = (*(btree->comp)) (data, cur->data);
      if (result == 0)
	return cur;
      else if (result < 0)
	cur = cur->left;
      else
	cur = cur->right;
    }

  return NULL;
}

struct btree_node * 
find_min (Btree *btree)
{
  struct btree_node *cur;

  if (btree->root != NULL)
    {
      cur = btree->root;

      /* Find the left most node. It will be the 'first'. */
      while (cur->left != NULL)
	cur = cur->left;

      return cur;
    }
  else
    return NULL;
}

struct btree_node * 
find_max (Btree *btree)
{
  struct btree_node *cur;

  if (btree->root != NULL)
    {
      cur = btree->root;

      /* Find the right most node. It will be the 'last'. */
      while (cur->right != NULL)
	cur = cur->right;

      return cur;
    }
  else
    return NULL;
}

void *
remove_node (Btree *btree, struct btree_node *cur)
{
  struct btree_node *child;
  void *data;

  btree->size--;

  if (cur->left != NULL && cur->right != NULL)
    {
      void *swap;
      struct btree_node * pred;

      /* Get In Order Predecessor. */
      pred = cur->left;
      while (pred->right != NULL)
	pred = pred->right;


      swap = cur->data;
      cur->data = pred->data;
      pred->data = swap;

      cur = pred;
    }

  /* Get the child. */
  child = (cur->right == NULL ? cur->left : cur->right);

  /* Perform the replace function based on type. */
  switch (btree->type)
    {
    case BST:
      replace_node (btree, cur, child);
      break;
    case RB:
      if (node_color (cur) == RBBTREE_BLACK)
	{
	  cur->state = node_color (child);
	  rbbtree_remove_case1 (btree, cur);
	}

      replace_node (btree, cur, child);

      if (cur->parent == NULL && child != NULL)
	child->state = RBBTREE_BLACK;

      break;
    }

  data = cur->data;

  free (cur);

  return (void *)data;
}

struct btree_node * 
parent (struct btree_node *node)
{
  assert (node != NULL);
  assert (node->parent != NULL);

  return node->parent;
}

struct btree_node * 
grandparent (struct btree_node *node)
{
  assert (node != NULL);
  assert (parent (node) != NULL);
  assert (parent (parent (node)) != NULL);

  return parent (parent (node));
}

struct btree_node * 
sibling (struct btree_node *node)
{
  assert (node != NULL);
  assert (parent (node) != NULL);

  if (node == parent (node)->left)
    return parent (node)->right;
  else
    return parent (node)->left;
    
}

struct btree_node * 
uncle (struct btree_node *node)
{
  assert (node != NULL);
  assert (parent (node) != NULL);
  assert (grandparent (node) != NULL);

  return sibling (parent (node));
}

void
rotate_left (Btree *btree, struct btree_node *pivot)
{
  struct btree_node *right;

  /* See: http://en.wikipedia.org/wiki/Tree_rotation for why these work. */

  right = pivot->right;

  replace_node (btree, pivot, right);

  pivot->right = right->left;

  if (right->left != NULL)
    right->left->parent = pivot;

  right->left = pivot;
  pivot->parent = right;
}

void
rotate_right (Btree *btree, struct btree_node *pivot)
{
  struct btree_node *left;
  
  /* See: http://en.wikipedia.org/wiki/Tree_rotation for why these work. */

  left = pivot->left;

  replace_node (btree, pivot, left);

  pivot->left = left->right;

  if (left->right != NULL)
    left->right->parent = pivot;

  left->right = pivot;
  pivot->parent = left;
}

void
replace_node (Btree *btree, struct btree_node *onode,
	      struct btree_node *nnode)
{
  /* Check to see if we are swapping the root. */
  if (onode->parent == NULL)
    btree->root = nnode;
  else
    {
      if (onode == parent (onode)->left)
	parent (onode)->left = nnode;
      else
	parent (onode)->right = nnode;
    }

  if (nnode != NULL)
    nnode->parent = onode->parent;
  
}

